//
// Created by user on 2022/3/9.
//
#include <vector>
using namespace std;
void compare(){

}

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    if (nums.size()<3){
        return res;
    }
    sort(nums.begin(), nums.end());
    for (int i=0; i< nums.size()-2; i++) {
        //在i+1 .... nums.length-1中查找相加等于-nums[i]的两个数
        if (i > 0 && nums[i] == nums[i - 1])continue;
        int target = -nums[i];
        int left = i + 1;
        int right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                res.push_back({nums[i], nums[left], nums[right]});
                //去重复
                while (left < right && nums[left] == nums[++left]);
                while (left < right && nums[right] == nums[--right]);
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}